package sol.leetcode;

import java.util.Arrays;

/**
 * House Robber II
 */
public class Issue213 {
    public int rob(int[] nums) {

        if (nums.length < 1)
            return 0;
        if (nums.length == 1)
            return nums[0];

        int m = rob(nums, 0, nums.length - 1);
        int n = rob(nums, 1, nums.length);
        return Math.max(m, n);
    }

    public int rob(int[] nums, int start, int end) {
        int len = end - start;
        if (len == 1)
            return nums[start];

        int[] storage = new int[len + 1];
        storage[0] = 0;
        storage[1] = nums[start];
        for (int i = 2; i <= len; ++i) {
            int with = storage[i - 2] + nums[start + i - 1];
            int without = storage[i - 1];
            storage[i] = Math.max(with, without);
        }

        System.out.println(Arrays.toString(storage));

        return storage[len];
    }

    public static void main(String[] args) {
        int[] nums = {2, 3};
        Issue213 sol = new Issue213();
        System.out.println(sol.rob(nums));
    }
}
